// @algorithm @lc id=264 lang=cpp 
// @title ugly-number-ii


#define print(...)
// @test(10)=12
// @test(1)=1
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1, 1);
        int nug[] = {1, 1, 1};
        for(int i=2; i<=n; i++){
            int cug[] = { dp[nug[0]]*2,  dp[nug[1]]*3, dp[nug[2]]*5 };
            dp[i] = *min_element(begin(cug), end(cug));
            for(int j=0; j<size(cug); j++){
                if(dp[i] == cug[j]){
                    nug[j]++;
                    print("dp[", i, "]=", dp[i],
                        ", cug=", Array(cug),
                        ", nug=", Array(nug), "\n")
                }
            }
        }
        return dp[n];
    }
};